Communication and computer networks (as parts of an information system) are vulnerable to attacks by hackers and malicious insiders as witnessed e.g. by electronic fraud, eavesdropping, computer viruses, and malicious applets. As our society depends more and more in a critical way on electronic information (electronic commerce, Electronic Data Interchange, intranets, electronic payments, electronic voting), more research is required to develop techniques to protect this information. Cryptology places a central role in all these solutions.
With the current state of the art in cryptology, it is not always possible to have provably secure solutions, although there is a trend to provide more and more security properties of cryptographic objects. A different approach to the problem of security is to show that a cryptographic object is resistant to various kinds of known attacks.
In the last decade, interest has been growing in the use of chaos for spread-spectrum communications and cryptography. All algorithms for cryptography proposed to date and based on chaos properties have a serious drawback in that security of the algorithms is not properly addressed. Security in cryptography means “randomness increasing” and “computationally unpredictable” behavior of the algorithm. Usual requirements for “statistical security” (used for Monte Carlo simulations) such as uniform distribution and independence from the plaintext (information) are only necessary conditions for cryptographic security.
L. Blum, M. Blum, and M. Shub, “A Simple Unpredictable Pseudo-Random Number Generator”, SIAM J. Comp. 15, pp. 364–83 (1986) considered two examples that both produce long well-distributed sequences of numbers (uniformly distributed and independent on the initial condition) and both have computationally hard problems at their core, but one of them is completely predictable (and therefore of no use in cryptography) and another is unpredictable.
In the following we briefly discuss some of the work on chaos based cryptography done in the last decade.
In papers such as R. A. J. Matthews, “On the Derivation of a ‘Chaotic’ Encryption Algorithm”, Cryptologia, vol. 13, pp. 29–42, 1989; D. D. Wheeler, “Problems with Chaotic Cryptosystems”, Cryptologia, vol. 13, pp. 243–50, 1989; and D. D. Wheeler and R. A. J. Matthews, “Supercomputer Investigations of a Chaotic Encryption Algorithm”, Cryptologia, vol. 15, no. 2, pp. 140–52, April 1991, the authors propose a chaos derived pseudo-random number generator (PRNG).
They numerically observe that the average cycle and transient lengths grow exponentially with the precision of implementation, and from this fact they deduce that by using high-precision arithmetics one can obtain PRNGs which are still of cryptographic interest.
The statistical tests applied to PRNGs for use in Monte Carlo simulations are generally simple; for cryptographic applications, PRNGs must pass far more stringent statistical tests as discussed e.g. in J. C. Largaris, “Pseudo-Random Number Generators in Number Theory and Cryptography”, in Cryptology and Computational Number Theory, C. Pomerance, ed., Proc. Symp. Appl. Math., 42, pp. 115–43 (1990). However, the authors of the captioned articles on PRNG do not address this question at all.
In a series of papers such as M. Goetz, K. Kelber, and W. Schwarz, “Discrete-time chaotic encryption systems—Part I: Statistical Design Approach”, IEEE Tran. On Circuits and Systems, part 1, 44, pp. 963–70,1997; F. Dachselt, K. Kelber, and W. Schwarz, “Discrete-time chaotic encryption systems—Part III: Cryptographical analysis”, IEEE Trans. On Circuits and Systems, part I, 45, pp. 883–88, 1998, chaotic cryptography is proposed.
By chaotic cryptography a continuous-value approach to the encryption problem is meant involving a discrete-value realization by means of floating-point or fixed-point arithmetics.
At the theoretical level, cryptography can be analyzed in two different ways: assuming that the underlying models of computation are Turing machines (see e.g. J. Hopcroft and J. Ullman, Formal Languages and Their Relations to Automata, Addison-Wesley, Reading, Mass., 1981) or real numbers (see e.g. L. Blum, F. Cucker, M. Shub and S. Smale, Complexity and real computation, Springer-Verlag, N.Y., 1998).
While the former approach (using Turing machines) has led to a notion of “secure cryptography” or “provable security”, no work in cryptography that assume real-numbers model of computation is known.
Also, the notion of security in several of the papers considered in the foregoing has only “statistical meaning” and includes two requirements: the probability distribution of the encoded signal is independent of the probability distribution of the information signal, and the probability distribution of the encoded signal is uniform.
At the practical level all cryptographical models are defined on finite sets. One of the goals in cryptography is to design good cryptographic algorithms using the smallest possible values of cardinality for these finite sets. However, discrete-value realization by means of floating-point (or fixed-point) arithmetics implies using a large finite set.
As indicated, chaos has already been used to design cryptographic systems. An encryption algorithm that uses the iterations of the chaotic tent map is proposed in T. Habutsu, Y. Nishio, I. Sasase, and S. Mori, “A Secret Key Cryptosystem by Iterating a Chaotic Map”, Advances in Cryptology—EUROCRYPT'91, pp. 127–40, Springer-Verlag, Berlin, 1991, and then generalized in Z. Kotulski and J. Szczepanski, “Discrete chaotic cryptography”, Ann. Physik, 6, pp. 381–94 (1997).
Encryption algorithms based on multiple iteration of a certain dynamical chaotic system coming from gas dynamics models are presented in Z. Kotulski J. Szczepanski, K. Grski, A. Paszkiewicz and A. Zugaj, “Application of Discrete Chaotic Dynamical Systems in Cryptography—DCC Method”, Internat'l Journ. of Bifurcation and Chaos, 9, pp. 1121–35 (1999).
In J. Fridrich, “Symmetric Ciphers Based on Two-Dimensional Chaotic Maps”, International Journal of Bifurcation and Chaos, 8, pp. 1259–84 (1998) methods are shown how to adapt invertible two-dimensional chaotic maps on a torus or on a square to create new symmetric block encryption schemes.
In M. S. Baptista, “Cryptography with chaos”, Phys. Lett A, 240, pp.50–54, 1998, the author encrypts each character of the message as the integer number of iterations performed in the logistic equation. While in conventional cryptographic ciphers the number of rounds (iterations) performed by an encryption transformation is usually less then 30 (e.g. DES usually requires 20 rounds), in the last-captioned paper this number can be as large as 65536, and is always larger than 250.
Another encryption algorithm based on synchronized chaotic systems is proposed in Y. H. Chu and S. Chang, “Dynamical cryptography based on synchronized chaotic systems”, Electron Lett., 35, pp. 974–75, 1999. The authors suggest each byte of a message be caused to correspond (to be encrypted) with a different chaotic attractor.
In E. Alvarez, A. Fernandez, P. Garcia, J. Jimenez, A. Marcano, “New approach to chaotic encryption”, Phys. Lett A, 263, pp. 373–75,1999, the authors assume that the message to be sent is a binary file consisting of a chain of 0's and 1's and the sender and the receiver has previously agreed to use the same d- dimensional chaotic dynamical rule, which generates sequences of real numbers by iterating it.
A common attribute to all chaos-based block encryption algorithms is that their security is not analyzed in terms of the techniques developed in cryptanalysis. For example, the encryption algorithm proposed in the paper by Habutsu et al. referred to in the foregoing is cryptanalysed in E. Biham, “Cryptanalysis of the Chaotic-Map Cryptosystem Suggested at EUROCRYPT '91”, Advances in Cryptology—EUROCRYPT '91, pp. 532–34, Springer-Verlag, Berlin, 1991, showing that the algorithm can be broken using known-plaintext attack.
In fact, analysis of performance and security of chaos based encryption schemes proposed in the papers by Baptista, Chu et al., and Alvarez et al. cited in the foregoing shows that the encryption rates these algorithms offer are not competitive with the encryption rates of standard cryptographic algorithms, and, furthermore, these algorithms can be easily broken using known-plaintext attacks.